package com.study.sort;

public class QuickSort extends Sort {

    @Override
    protected void sort(int[] list) {
        quickSort(list);
    }

    @Override
    protected String sortName() {
        return "quick sort";
    }

    private void quickSort(int[] list) {
//        quickSort(list, 0, list.length - 1);
        qs(list, 0, list.length - 1);
    }


    private void qs(int[] list, int l, int r) {
        if (l >= r) {
            return;
        }

        int p = list[r];
        int m = l;
        for (int i = m; i < r; i++) {
            if (list[i] < p) {
                int temp = list[i];
                list[i] = list[m];
                list[m] = temp;
                m++;
            }
        }
        list[r] = list[m];
        list[m] = p;

        qs(list, l, m - 1);
        qs(list, m + 1, r);
    }


    private void quickSort(int[] list, int s, int e) {
        if (s >= e) {
            return;
        }
        //划分两个子数组,通过p点
        int p = partition(list, s, e);
        quickSort(list, s, p - 1);
        quickSort(list, p + 1, e);
    }

    private int partition(int[] list, int s, int e) {
        //以pivot 为轴,巧妙地移动数组.原地排序
        int pivot = list[e];
        int j = s;
        //从左边开始,比pivot小的被换到左边, 然后指针j向右移动,此时j的左边都是比pivot小的元素
        for (int i = s; i < e; i++) {
            if (list[i] < pivot) {
                swap(list, j, i);
                j++;
            }
        }
        //置换完成以后,把pivot换到此时j的位置,刚好左边都是比pivot小的元素
        swap(list, j, e);
        return j;
    }
}
